package com.zfcer.chapter02;

import sun.security.util.Length;

/**
 * @Classname ListNode
 * @Description 链表数据结构
 * @Created by zfcer
 * @Date 2022/4/16 11:31
 */
public class List {
    ListNode dummy, tail; // 虚拟头结点和尾结点
    int size = 0;

    public List() {
        this.dummy = new ListNode(0);
        this.tail = this.dummy;
    }

    /**
     * tail后添加节点
     * @param node
     */
    public boolean add(ListNode node){
        return addIdx(size, node);
    }


    /**
     * 指定位置后添加节点
     * @param idx
     * @param node
     */
    public boolean addIdx(int idx,ListNode node){
        if(idx >= size) return false;
        // 尾插法
        if(idx == size - 1){
            this.tail.next = node;
            this.tail = node;
        }
        // 头插法
        else if(idx == 0){
            node.next = dummy.next;
            dummy.next = node;
        }
        // 中间位置插入
        else {
            ListNode pre = dummy;
            for(int i=0; i<idx; i++){
                ListNode p = pre.next;
                pre = p;
            }
            node.next = pre.next;
            pre.next = node;
        }
        size++;
        return true;
    }

    /**
     * 删除tail元素
     * @return
     */
    public boolean remove(){
        if(size <= 0) return false;
        ListNode pre = dummy;
        ListNode p = pre;
        while(p.next != null){
            p = p.next;
            pre = p;
        }
        pre.next = null;
        size--;
        tail = pre;
        return true;
    }

    /**
     * 修改node值
     */
    public void update(ListNode p, int val){
        if(p == null) return;
        p.val = val;
    }

    /**
     * 查询idx位置元素值
     * @param idx
     * @return
     */
    public int select(int idx){
        if(idx < 0 || idx >= size) return 0;
        ListNode p = dummy.next;
        for(int i=0; i<=idx; i++)
            p = p.next;
        return p.val;
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}
